BOJ_1780_종이의개수

분할 정복(Divide and Conquer)으로 종이를 쪼개서 푸는 문제
부분 문제가 중복되지 않는다는 분할 정복의 특징처럼, 큰 영역에서 조건을 만족한 종이라면 더 이상 쪼개지 않는다. 각 문제가 서로 영향을 주지 않기 때문에 조건을 만족하는지 검증하는 단계에서 독립적으로 종이 개수를 세어주면 된다.

size = N에서부터 종이에 적힌 숫자가 모두 일치하는지 확인한 후, 일치하지 않는다면 일치하지 않은 종이가 나온 영역에 대해 size를 3으로 나눠서 탐색을 한다.
size가 1이면 탐색에 성공하기 때문에 종료 조건을 줄 필요는 없다.

package BJO;  
  
import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.stream.Stream;  
  
public class BJO_1780_종이의개수 {  
  
static int N;  
static int[][] paper;  
static int[] count = new int[3]; // -1 0 1  
  
	public static void main(String[] args) throws IOException {  
	// N은 3의 배수  
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
		N = Integer.parseInt(br.readLine());  
		  
		// 입력  
		paper = new int[N][N];  
		for (int i = 0; i < N; i++) {  
		paper[i] = Stream.of(br.readLine().split(" ")).mapToIntparseInt).toArray(;  
		}  
		  
		// 검사검사  
		dfs(0, 0, N, N, N);  
		System.out.println(count[0]);  
		System.out.println(count[1]);  
		System.out.println(count[2]);  
	}  
  
	static void dfs(int startY, int startX, int endY, int endX, int size) {  
		for (int i = startY; i < endY; i += size) {  
			for (int j = startX; j < endX; j += size) {  
				if (!checkSameNumber(i, j, size)) {  
					dfs(i, j, i + size, j + size, size / 3);  
				}  
			}  
		}  
	}  
  
	static boolean checkSameNumber(int y, int x, int size) {  
		int num = paper[y][x];  
		for (int i = y; i < y + size; i++) {  
			for (int j = x; j < x + size; j++) {  
				if (num != paper[i][j]) {  
					return false;  
				}  
			}  
		}  
	  
		count[paper[y][x] + 1]++;  
		return true;  
	}  
}

분할 정복 과정에서 아래와 같이 작성하면 파라미터 개수를 줄이고 더 간단하게 코드를 짤 수 있다

static void divide(int y, int x, int n){  
	int m = n/3;  
	for(int i=0; i < 3; i++){  
		for(int j=0; j < 3; j++) {  
			divide(arr, ans, y+i*m, x+j*m, m);  
		}  
	}  
}